Yes, in this sentence, tout is an adverb. Adverbs are invariable. So :

Je trouvais l’histoire tout entière incroyable.

Les règles d’accord des adverbes haut et tout, placés devant un adjectif, sont différentes.

Haut, adverbe placé devant un adjectif, est toujours invariable.

Ces personnes sont haut placées.

La règle d’accord de tout adverbe placé devant un adjectif est :

Tout, adverbe, est invariable sauf quand il est placé devant un adjectif féminin commençant par une consonne ou un h aspiré, ceci pour des raisons d’euphonie.

Donc :

• l’histoire tout entière est incroyable (Adjectif commençant par une voyelle.)
• Elles étaient toutes honteuses d’avoir oublié l’heure. (Adjectif féminin commençant par un h aspiré : accord.)
• Elles étaient toutes contentes de leur réussite. (Adjectif féminin commençant par une consonne : accord.)
• Ils étaient tout honteux d’avoir oublié l’heure. (Adjectif masculin, pas d’accord.)
• Elles étaient tout heureuses de me voir arriver si tôt. (Adjectif commençant par un h muet : pas d’accord.)

Attention à  :

Elles étaient toutes honteuses d’avoir oublié l’heure.
Elles étaient toutes contentes de leur réussite.

où à l’écrit toutes peut se comprendre comme un pronom (→ chacune d’entre elles) ou comme un adverbe (toutes modifiant l’adjectif). Le contexte permet en général d’éclairer.

À l’oral la diction des deux cas est différente.
Dans le cas où toutes est employé comme pronom le mot est accentué (accent tonique de fin de groupe de souffle) et on marque un bref arrêt après toutes. Dans le cas où toutes est employé comme adverbe, non seulement le mot n’est pas accentué et on ne marque pas le léger arrêt mais dans le cas d’un h aspiré certains vont même faire une liaison : /tutɔ̃tøz/ (toutes honteuses).

Historique de la règle : en ancien français, tout (comme tous les adjectifs employés comme adverbes) s’accordaient dans tous les cas. La règle observée aujourd’hui a été élaborée dans ses grandes lignes par Vaugelas et précisée peu après par l’Académie.
Cette règle issue d’un compromis (voir les liens donnés ci-dessus) étant assez arbitraire ça explique les incertitudes de l’usage, innombrables au XVII^e siècle (voir Racine) et encore fréquents au XIX^e siècle (voir Balzac). De nos jours, la règle est établie et en dehors d’être ce que l’Académie Française appelle « un bon auteur » que personne n’ira juger pour la qualité de sa langue il est conseillé de la respecter dans un contexte où on sera évalué sur la correction de son expression écrite.

Both forms are generally accepted in the first case.

Despite being an adverb, tout becomes toute when followed by a feminine adjective starting with a consonant or a non mute h.

When the adjective starts with a vowel, the rule since the end of the 17th century is to stay invariable but tout might still optionally agree with the adjective like it used to do in the past. e.g. from the Littré:

Et puisque vous voyez mon âme toute entière…. [Corneille, Nicom. III, 2]

D’un repas sortant toute enfumée, [Boileau, Sat. X]

This final -e is controversial, some dictionaries no more mention its possibility.

Edit: The final -e is actually considered to be a mistake nowadays. I stand corrected by Laure.

_{Quite an absurd/inconsistent grammatical rule IMHO…}