« Faire son mieux » n’est pas exact ; il faut toujours écrire « faire de son mieux » (Wiktionnaire).
C’est une locution qui n’est pas absolument figée. L’adjectif possessif s’accorde et le verbe se conjugue.

Non, cette locution n’a pas de connotations négatives. Cependant, elle est utilisée dans des contextes où la personne ou les personnes qui font de leur mieux ne font pas nécessairement quelque chose de très bon ou de très bien comme elle peut aussi s’employer dans ces contexte où c’est tout le contraire.

On voit d’après les exemples du Wiktionnaire que le verbe peut avoir un complément.

• Sois donc attentif, mon garçon ; sois docile ; fais de ton mieux ce que tu dois faire. Dans la vie, tout est là ! — (Hector Malot, Sans famille, 1878)
• Quand je fus assuré que le silence était bien revenu, je saisis un canif et fis de mon mieux pour tenter de m’entailler la jambe droite. Mais la lame était émoussée et je manquais de cœur à l’ouvrage. — (Graham Greene, Une sorte de vie, traduit de l’anglais par Georges Belmont & Hortense Chabrier, éd. Robert Laffont, 1971, chapitre 3, §. 1)S

Dans le premier exemple le verbe a un COD (ce que tu dois faire), dans le second c’est un CC de but (pour tenter de m’entailler la jambe droite).

En plus des exemples du Wiktionnaire

• Il a fait de son mieux mais ce n’est pas suffisant.
• Il vous sera demandé de faire de votre mieux.
• Les peintres ont fait de leur mieux et leur travail peut être considéré comme irréprochable.

C’est une expression subjective qui exprime une certaine indécision, sans doute à cause d’une issue incertaine. Sinon, on emploierait des expressions similaires comme faire au mieux ou faire pour le mieux.

Faire de son mieux sous-entend une obligation de moyens, pas de résultats.

Lorsque le donneur d’ordre s’attend à un résultat, il peut considérer que faire de son mieux est insuffisant. Il préfèrera alors choisir un autre prestataire qui garantit les résultats.

There has been some controversy in the chat while discussing about whether faire de son mieux has a negative connotation or not.

In my opinion, the key word is the possessive here: mon mieux, ton mieux, son mieux, leur mieux…

It emphasizes the fact someone’s best is not the best but a personal upper limit that is not pushed by them.

Je ne suis pas à tout moment ce que je devrais être. Je fais de mon mieux, alors que très souvent je pourrais faire mieux que mon mieux.
Marguerite Yourcenar, Les yeux ouverts, 1980.

Parfois, nous pouvons prononcer des mots avec des bonnes intentions mais les formulations maladroites peuvent aboutir à l’inverse du résultat souhaité. C’est le cas avec la formule “fais de ton mieux”. Caroline, Apprendre, réviser, mémoriser., 2018

Un professeur qui dit d’un élève "il fait de son mieux" ne vole pas très haut dans le registre des louanges. Inconnu, Etudes littéraires.

"La situation est difficile, il fait de son mieux." C’est ainsi que Dominique Strauss-Kahn évoque l’action de François Hollande, L’Express, 2013

Mais Massimo Furlan, ou plutôt la créature qu’il convoque pour l’occasion, Pino Tozzi, est d’une certaine manière incompétent : il ne parle ni portugais ni finlandais, ne chante pas très bien, même s’il fait de son mieux, après de nombreuses répétitions. Festival d’avignon. 2010

Arrivé sur ce Tour de France avec l’ambition de faire de son mieux mais sans penser une seule seconde qu’il pourrait le gagner dès sa première participation, Cyclism’Actu, 2020

This is why I consider that this expression has at least a slight negative connotation because under the hood it is condescending and says: I’m/you are/they are not able to do better.

What would have had an always positive connotation is:

Tu as bien fait. You did well.

Tu as réussi. You succeeded.

or even better:

Tu t’es surpassé. You outdone yourself.

On the other hand, tu as fait de ton mieux might still be considered as a mildly positive expression when used to comfort someone after a failure.

Ne sois pas déçu de n’avoir terminé que sixième, tu as fait de ton mieux. Don’t be disappointed only getting the sixth place, you did your best.

Stronger negative sentences would be:

Tu n’as pas fait de ton mieux. You "under-performed".

Tu n’as pas bien fait. You didn’t do well.