Den totala personalstyrkan i NHS Skottland är rekordhög, men revisorerna sade att regeringen måste planera framåt bättre för att "brådskande ta itu med personalfrågor".
Det sade att det fanns tecken NHS tjänster var "under ökande stress".
Den skotska regeringen sade att den var fast besluten att ha rätt blandning av kompetens och personal på rätt platser.
Men oppositionspartierna sade att den "dämpande" rapporten var en bekräftelse på en "djupare arbetskraftskris" inom hälso- och sjukvården.
I den nya rapporten, den första delen av en tvåstegsrevision av personalplanering i Skottlands NHS, undersöktes klinisk bemanning på sjukhus och andra lokaler för sekundärvård.
Den konstaterade att hälsonämnderna "konsekvent underskattar" det antal anställda de behöver, medan den skotska regeringen "ännu inte på ett tillfredsställande sätt har beräknat vilka effekter en ökad och föränderlig efterfrågan på NHS-tjänster skulle kunna få på den arbetskraft eller de färdigheter som krävs för att tillgodose detta behov".
Rapporten kommer efter medicinska ledare uppmanade beslutsfattare att vara "frälsande" över NHS-reformen i framtida budgetar, bland varningar från fackföreningar att "NHS i Skottland inte får de resurser det behöver".
I rapporten, av Auditor General Caroline Gardner, sades det att det var viktigt att regeringen och NHS chefer planerar mer effektivt för framtiden.
Det betonades att utgifterna för NHS-personal hade ökat med 11 % mellan 2011-12 och 2016-17, med en rekordhög personalstyrka på 139 341 heltidsanställda.
Men genom att nå dessa personalnivåer har nästan alla NHS styrelser överutnyttjats mot sina lönebudgetar, och byråns personalkostnader har mer än fördubblats under sex år till mer än 171 miljoner pund.
Och rapporten varnade för att regeringen och NHS styrelser "inte har planerat sin NHS personal effektivt på lång sikt".
Det sades att hälso- och sjukvården står inför "brådskande" personalutmaningar, bland annat:
Den skotska regeringen inrättar en nationell arbetsgrupp för att förbättra det gemensamma arbetet. I Gardners betänkande sades det dock att ansvaret för arbetskraftsplanering var "förvirrat" - det är för närvarande uppdelat mellan regeringen, hälso- och sjukvårdsnämnderna och de regionala arbetsgrupperna - och att det fanns en risk för att det skulle splittras ytterligare med integreringen av hälso- och sjukvårdstjänster och socialvårdstjänster.
Anna Gardner sade: " Tusentals människor arbetar hårt i Skottlands nationella hälso- och sjukvårdssystem för att tillhandahålla viktiga offentliga tjänster varje dag, men det finns tecken på att hälso- och sjukvården är stressad och att personalen utsätts för allt större belastningar.
"Den skotska regeringen och NHS:s styrelser inser utmaningarna, men de måste snarast förbättra sin förståelse för framtida efterfrågan, personalprognoser och tillhörande kostnader, och i detalj ange hur de planerar att skapa en arbetskraft som kan tillgodose befolkningens långsiktiga hälsobehov."
Rapporten välkomnades av personalgrupper och fackföreningar.
Theresa Fyffe, chef för Royal College of Nursing Scotland, sade att rapporten bör belysa "den brådska med vilken arbetskraftsplanering nu måste åtgärdas".
Hon sade: " Audit Scotland har slagit spiken i huvudet. Alltför långa planer har begränsats av vad som är överkomligt och genomförbart med den tillgängliga personalen, snarare än att fokusera på strategisk, långsiktig planering för att möta efterfrågan. Följden blir att Skottland har för få vårdpersonal och för få sjuksköterskor som utbildas.
"Staff över hela NHS Skottland är under enorm, outtröttlig press för att möta den ständigt växande efterfrågan. De betydande utmaningar för arbetskraften som beskrivs i rapporten måste hanteras på ett kraftfullt, realistiskt och snabbt sätt om patienterna ska få den vård de behöver."
Dr Peter Bennie, ordförande för British Medical Association Scotland, sade att det fanns "allvarliga utmaningar för arbetskraften som hälso- och sjukvården i Skottland måste ta itu med av den skotska regeringen som en brådskande fråga".
Och Matt McLaughlin, Unison Skottlands hälsochef, sade att det fanns "inget tvivel om att tjänsten behöver för att avsevärt öka sitt spel när det gäller personalplanering".
Han tillade: "Management team, personal och fackföreningar uppmanas att rädda miljoner, upprätthålla tjänster på nuvarande nivå och planera för en annan framtid. Den verkligheten innebär att arbetskraftsplanering dras åt olika håll eftersom kortsiktiga behov väger tyngre än långsiktig planering.
Hälsominister Shona Robison berättade för BBC Scotland att hon accepterade alla rekommendationer i rapporten.
Robison påpekade att regeringen offentliggjorde den första delen av sin nationella plan för hälso- och sjukvård och social omsorg i juni, där det fastställs hur man kan förbättra planeringen för att rekrytera, utveckla och behålla personal.
Hon sade: "Vi har lyssnat till Audit Scotland kommentarer om personalplanering långt innan de har producerat denna rapport. Därför arbetade vi med en mycket detaljerad arbetsstyrkasplan som ger en mycket tydlig ram för hur vi gör förbättringarna, hur vi bygger vidare på det arbete som redan gjorts, men tar ett verkligt regionalt och nationellt perspektiv på detta.
"Inte bara för nuvarande servicemodeller, utan även för framtida servicemodeller. Och det är därför detaljerna har gjorts och nu kommer att föras framåt. Den takt som ligger bakom kommer absolut att finnas där.
"Jag förstår behovet av att inte bara ha mer personal, men att ha rätt personal på rätt platser, att uppfylla denna nya modell för att hålla människor utanför sjukhuset, hålla människor i samhället, och det är vad vi ger noggrann uppmärksamhet."
Oppositionspartierna sade att rapporten var ett bevis på en "arbetskraftskris" inom NHS.
Scottish Conservative Health talesman Miles Briggs sade: " Gång på gång har vi sett varningar om långsiktig personalplanering, och dessa siffror visar att situationen bara blir värre.
"Byggnadskostnaderna ökar kraftigt, och andelen lediga tjänster inom konsult- och sjukskötersketjänster har mer än fördubblats. Ännu mer oroande är att vi inte ser tillräckligt många nya sjuksköterskor utbildas för att hålla jämna steg med en allt äldre arbetskraft."
Scottish Labours Anas Sarwar sa att rapporten var "helt fördömande" och att NHS personal var "överarbetad, undervärderad och underrepresenterad".
Han sa: "Staff moral är på botten i hälso-och sjukvården, med personal rapporterar det helt enkelt inte tillräckligt av dem att göra jobbet ordentligt."
Och Lib Dem MSP Alex Cole-Hamilton sade: "Denna fördömande granskning tar med rätta en dunkel syn på Nicola Sturgeon och hennes hälsovårdssekreterares försök att avvärja denna kris. Den skotska regeringen ignorerade varningen efter att ha varnat för att bemanningen inte håller jämna steg med efterfrågan."
Skottlands regering och hälso- och sjukvårdsnämnder har misslyckats med att planera effektivt för långsiktiga personalutmaningar, har Audit Skottland sagt.