Le Bulgare, 13e tête de série, qui a mis fin à six ans de disette à Brisbane ce mois-ci, s'est imposé 4-6, 6-3, 7-6 (7/1), 6-2 dans une John Cain Arena brûlée par le soleil.
Le vétéran de 32 ans a déclaré qu'il avait eu du mal à s'adapter aux conditions difficiles, mais qu'il était sûr d'être en bonne forme physique.
"Je savais que mon jeu n'était pas au point, mais je pouvais compter sur quelque chose d'autre, à connaître ma forme aujourd'hui", a-t-il déclaré.
Dimitrov, dont le meilleur résultat à Melbourne est une demi-finale, a commencé le match de la pire des manières, perdant les huit premiers points alors qu'il avait du mal à trouver son rythme.
Fucsovics a fait un nouveau break pour s'emparer de la manche et a commencé à profiter de 19 fautes directes dans la raquette de Dimitrov.
Dimitrov était menacé d'une sortie prématurée lorsqu'il a été breaké au début du deuxième set, mais il a tout de suite réagi et a répété l'exploit pour égaliser.
Aucun des deux joueurs n'a été en mesure de faire le break dans un troisième set serré, mais Dimitrov a pris le contrôle du tie-break et est reparti avec un seul point de retard.
L'ancien numéro trois mondial était désormais méconnaissable par rapport au joueur qui a commencé le match.
Il a breaké son adversaire hongrois à deux reprises dans le quatrième set et a réduit son nombre de fautes directes à seulement six, remportant le set 6-2 et s'assurant ainsi la victoire.
Dimitrov affrontera Sebastian Ofner ou Thanasi Kokkinakis au deuxième tour.