ScotNursing säger att det bara kan fylla ca 40% av tillgängliga skift, medan det tidigare kunde fylla 90%.
Företaget uppmanar tidigare sjuksköterskor att överväga att göra enstaka skift.
Den skotska regeringen sade att den hade vidtagit åtgärder för att stödja sjuksköterskor, och öka antalet sjuksköterskor och barnmorskor som arbetar i NHS.
ScotNursing verkställande Ann Rushforth sade problemet var ner till bristen på elever som slutar skolan börjar yrket.
Hon sade: " Det tar fyra år att utbilda en sjuksköterska. Sorgligt nog verkar inte skollediga vilja vara sjuksköterskor nu för tiden. De vill bli veterinärsköterskor och supermodeller."
Mrs Rushforth uppmanade sjuksköterskor som fortfarande är registrerade men som kan ha tagit en paus för att ha en familj eller för att arbeta i ett vårdhem att överväga att uppdatera sina kliniska färdigheter.
"Människor kan göra en betydande skillnad genom att göra bara ett skift i månaden", sade hon.
"Det finns hundratals lediga platser som vi inte kan fylla men detta arbete måste fortfarande göras av någon. Människor kanske inte inser att de inte får det stöd de borde ha."
Under den allmänna valkampanjen lovade både det skotska Labourpartiet och de skotska konservativa att anställa ytterligare 1 000 sjuksköterskor i Skottland.  Rushforth sade dock att problemet är en allvarlig brist på kvalificerad personal.
"Nursorna är inte som snabbkaffe. Du kan inte bara göra dem. Särskilt sjuksköterskor som är villiga att göra enstaka skift har blivit lika sällsynta som pandor."
ScotNursing diskuterar med vidareutbildningsanstalter om att erbjuda enkla vägar för sjuksköterskor att uppdatera sina färdigheter.
Sjuksköterskorna måste arbeta minst ett antal timmar per år och ha genomgått lämplig utbildning för att kunna arbeta i NHS. ScotNursing sade enstaka skift kan hjälpa dem att uppnå detta.
I september förra året fanns det 58 000 sjuksköterskor och barnmorskor anställda i NHS i Skottland, jämfört med 55 000 år 2005.
Siffror från NHS statistik avdelning, ISD, föreslog ytterligare 429000 personer sågs som slutna patienter och öppenvårdspatienter under samma period.
Detta visar att det bara finns en extra sjuksköterska för 143 närvarande.
Royal College of Nursing (RCN) har varnat för att hälsonämnderna är under "ömsesidig press" att tillsätta lediga platser, men att antalet anställda inte håller jämna steg med ökningen av antalet patienter.
Direktören för RCN Scotland Theresa Fyffe sade: " Det råder inget tvivel om att det helt enkelt inte finns tillräckligt många sjuksköterskor för att fylla luckorna.
– Detta är ett resultat av den ökande efterfrågan på patienter, betydande nedskärningar av antalet sjuksköterskestudenter som rekryterades 2011/12 och 2012/13 och höga pensioner från vårdpersonalen.
"Det faktum att program för återinträde i arbetslivet har dragits tillbaka under årens lopp gör det svårt för sjuksköterskorna att komma tillbaka till arbetsstyrkan. Om dessa program fortfarande finns tillgängliga är de dock ett sätt att fylla dessa luckor.
– Men det vi behöver är att hälso- och sjukvårdsnämnderna på ett kraftfullt sätt tillämpar verktygen för sjuk- och barnmorskearbete och arbetsplanering. Det är det enda sättet att få rätt antal sjuksköterskor med rätt kompetens som arbetar på rätt ställe."
Den skotska regeringen sade att den åtog sig att ge sjuksköterskorna det stöd de behöver för att möta "de ökande kraven på hälso- och sjukvården".
Hälsominister Shona Robison sade: " Vi har ökat antalet sjuksköterskor och barnmorskor som arbetar inom NHS i Skottland med 2.300 under denna regering, till en ny rekordhög nivå på mer än 43.000 WTE kvalificerade sjuksköterskor och barnmorskor.
"Vi har nyligen meddelat 450.000 pund finansiering för en retur-till-praktik program under de kommande tre åren, samtidigt som en 3% ökning av pre-registrering elev intag som kommer att uppmuntra tidigare sjuksköterskor och barnmorskor att återvända till yrket. Detta system kommer att bidra till att cirka 75 före detta sjukvårdspersonal kommer tillbaka till yrket varje år.
"Vi fortsätter också att investera i en rad olika arbeten för att se till att vi rekryterar och behåller rätt antal anställda, och utrustar dem med de färdigheter de behöver för att ge högkvalitativ vård.
"Genom NHS Scotland s banbrytande omvårdnad Workforce Planning Tools, som utvecklats i samarbete med sjuksköterskeföreningar, hälsonämnder kan informera beslut om antalet sjuksköterskor som behövs för särskilda kliniska områden."
Skottlands största sjuksköterskebyrå har varnat för att det inte finns tillräckligt många kvalificerade sjuksköterskor i Skottland för att fylla rotaluckorna.