1958 zog Nellie Ruth King mit den beiden Söhnen nach Durham, Maine, damit sie sich um ihre alten Eltern kümmern konnte. (Drei Jahre später fand King seine Großmutter tot im Bett, erneut ein traumatisches Erlebnis, das er später in seiner Kurzgeschichte „Oma“ verarbeitete.) 1959 lernte er dort Christopher Chesley kennen, der sich ebenfalls für phantastische Literatur interessierte und Geschichten schrieb. Er entdeckte in einer alten Bücherkiste seines Vaters Titel des Horrorautors H.P. Lovecraft und den Avon Sampler, eine der frühesten Anthologien phantastischer Literatur. Natürlich gab es auch noch andere Quellen für phantastische Literatur: Im Nachwort zu FRÜHLING, SOMMER, HERBST UND TOD erinnert sich King nostalgisch-wohlig an das nervöse Warten auf den Postzusteller, der jede Woche die Saturday Evening Post mit den neuen Geschichten Ray Bradburys oder Clarence Buddington Kellands brachte.
King war zwar für sein Alter groß und stämmig, aber in der Kleinstadt Durham unter Gleichaltrigen schon allein wegen seiner Interessen in gewisser Hinsicht ein Außenseiter (ein weiteres späteres Motiv, von dem Romane wie CHRISTINE oder ES leben). Und er war oft krank, was ihm die Zeit gab, immer mehr zu schreiben; nachdem er dann eine Schreibmaschine geschenkt bekommen hatte, weitete sich seine literarische Aktivität zusehends aus. Zum einen schickte er schon mit zwölf Jahren seine Geschichten an Verleger (hauptsächlich an Genre-Magazine wie Fantastic und The Magazine of Fantasy and Science Fiction), zum anderen druckte er sie selbst auf der Offset-Presse seines Bruders (der darauf die kleine Zeitung Dave’s Rag herstellte, an der auch Stephen mitarbeitete) und versuchte, die einzelnen Exemplare auf dem Schulhof – er besuchte mittlerweile die High School Lisbon Falls – oder an Bekannte zu verkaufen. So erinnert er sich zum Beispiel an seine „Romanfassung“ (von zwölf Seiten) des Films Das Pendel des Todes, von der er 250 Exemplare druckte und in drei Tagen tatsächlich 70 Stück verkaufte. Gemeinsam mit Chris Chesley veröffentlichte er 1960 ein Fanzine mit dem Titel People, Places and Things, das achtzehn Storys von einer halben bis einer vollen Seite Umfang enthielt; acht dieser Geschichten stammen von King, eine neunte schrieb mit gemeinsam mit Chesley, die restlichen stammen von Chesley. 1963 erschien sogar eine zweite Auflage im „Verlag“ Triad Publishing Company, in dem 1964 dann auch „A Gaslight Book“ mit siebzehn anderthalbzeilig geschriebenen Textseiten erschien: The Star Invaders, eine Science-Fiction-Story des jungen Autors. Ein Jahr später veröffentlichte King seine erste Kurzgeschichte außerhalb seines Eigenverlags: In dem Comic-Fanmagazin Comics Review erschien seine Story „I Was a Teenage Grave Robber“, die der damalige Fan und heute sehr bekannte Comic-Autor Marv Wolfman 1966 in seinem Fanzine Stories of Suspense unter dem Titel „In a Half-World of Terror“ nachdruckte. 1965 schrieb King dann auch seinen ersten Roman, THE AFTERMATH, einen bis heute unveröffentlichten SF-Text um die Überlebenden eines Atomkriegs, die den Kampf gegen einen Supercomputer aufnehmen, der die neue Gesellschaft Nordamerikas endgültig ins Verderben zu ziehen droht. Auch für die Schülerzeitung The Village Vomit war King aktiv. Wegen einer Parodie, die er dort veröffentlichte, wurde er sogar vom Unterricht suspendiert.
Im Sommer 1966 schloss er die Highschool ab und wechselte im Herbst an die University of Maine in Orono in der Nähe von Bangor. Zuvor begann er seinen zweiten Roman mit dem Arbeitstitel GETTING IT ON, den er jedoch wieder abbrach; erst später beendete er ihn und veröffentlichte ihn nach einer Überarbeitung unter dem Pseudonym Richard Bachman und dem Titel RAGE. Auf der Universität belegte er in den ersten Semestern Kurse in zahlreichen Fächern, bevor sein Professor Jim Bishop ihn bestärkte, weiterhin zu schreiben. Er testete Drogen an, lernte Bier zu schätzen und veröffentlichte in Studentenzeitungen Geschichten und Artikel (die mit Freiexemplaren „honoriert“ wurden). Für die Universitätszeitschrift Maine Campus verfasste er eine Kolumne, „The Garbage Truck“. Oft tauchte er eine Stunde vor Redaktionsschluss im Büro auf, setzte sich hinter die Schreibmaschine und lieferte dann auf den letzten Drücker, aber stets pünktlich ab.
1967 erschien dann endlich – nach vielleicht sechzig Ablehnungen – seine erste Kurzgeschichte in einer anerkannten Zeitschrift: „The Glass Floor“ wurde für ein Honorar von 40 Dollar in dem von Robert A.W. Lowndes herausgegebenen Krimi-Magazin Startling Mystery Stories gedruckt. King hatte einen ersten Durchbruch erzielt.
Oft hat man dem Autor mit seinem ersten Roman, CARRIE, einen „Erfolg über Nacht“ konzediert. Doch Stephen King hat sein Lehrgeld bezahlt: Nach frühesten Fanzinestorys sammelte er Ablehnungsbescheide, profitierte er von Ratschlägen von Genremagazin-Herausgebern, veröffentlichte er in Schüler- und Universitätszeitschriften. Der Weg zum Ruhm war steinig, und das große Ziel war immer noch nicht in Sicht. King sah höchstens Licht am Ende des Tunnels, und noch immer reihte sich eine Enttäuschung an die andere. King schrieb den Roman THE LONG WALK und reichte ihn nach Ermutigung durch seine Professoren Burton Hatlen und Carroll Terrell bei einem Wettbewerb für angehende Schriftsteller ein. Er wurde jedoch per Formbrief abgelehnt.
King begann den Roman SWORD IN THE DARKNESS, der sich mit Rassenunruhen in einer Großstadt beschäftigt; er blieb bis heute unveröffentlicht. Er schrieb zahlreiche Gedichte, von denen der Großteil ebenfalls niemals veröffentlicht wurde, engagierte sich für die Antikriegsbewegung und wurde in den Studentensenat gewählt. Er belegte nun hauptsächlich Seminare im Fach Englisch und hielt selbst ein Seminar über Populäre Kultur und Literatur ab. Um sich finanziell über Wasser zu halten, arbeitete er in der Universitätsbibliothek, wo er 1969 die 1949 in Old Town in Maine geborene Tabitha Jane Spruce kennenlernte, die Interesse an dem langhaarigen, bärtigen, aber alles andere als wohlhabenden Studenten fand.
1970 schloss King den Roman SWORD IN THE DARKNESS ab. Durch Vermittlung eines Professors fand er eine literarische Agentur, die den Roman an ein gutes Dutzend Verlage schickte, doch er wurde überall abgelehnt. Am 5. Juni machte King seinen Abschluss als Bachelor of Arts in Englisch, was gleichbedeutend mit einer Lehrerlaubnis für Highschools war, wurde von der Musterungskommission (während des Vietnamkriegs galt in den USA die Wehrpflicht) als untauglich eingestuft und zog daraufhin nach Orono. Er begann mit der Arbeit an einem langen Roman um einen Revolverhelden, schrieb weitere Geschichten, die er nun auch an Herrenmagazine wie Cavalier verkaufte, fand keine Anstellung als Lehrer und arbeitete als Tankwart und in einer Industriewäscherei in Bangor. Finanziell ging es ihm herzlich schlecht; seine Jobs brachten zwischen 1,25 und 1,60 Dollar die Stunde, und die Magazine, die seine Geschichten akzeptierten, zahlten erst bei Erscheinen und nicht bei Annahme. Wie sich King im Nachwort zu seiner zweiten Kurzgeschichtensammlung, SKELETON CREW, erinnert, wurde er einmal wegen groben Unfugs verhaftet und zu einer Geldstrafe von 250 Dollar (die er natürlich nicht aufbringen konnte) oder einem Monat Haft verurteilt. Vier Tage vor Ablauf der Zahlungsfrist bekam er einen Scheck von der Herrenzeitschrift Adam über 250 Dollar. Die Geschichte „The Float“, der das Honorar galt, ist allerdings nach Kings Wissen niemals erschienen, und er hat sie dreizehn Jahre später unter dem Titel „The Raft“ neu geschrieben.
King ging inzwischen fest mit Tabitha Spruce, und am 2. Januar 1971 heirateten die beiden in Old Town. Sie arbeitete nebenbei als Kellnerin und machte im Mai ihren Abschluss in Geschichte; kurz darauf wurde ihr erstes Kind, die Tochter Naomi Rachel, geboren. King schloss nun GETTING IT ON ab und schickte es an den Verlag Doubleday; der Redakteur Bill Thompson lehnte es zwar ab, ermunterte King aber, ihm andere Manuskripte zu schicken.
Im Herbst 1971 fand King eine Anstellung als Englischlehrer an der Hampden Academy in Hampden, Maine, mit einem Jahresgehalt von 6400 Dollar. Die Familie zog ins benachbarte Hermon, und im Winter schrieb King einen weiteren Roman, den Thompson bei seinen Vorgesetzten nicht durchsetzen konnte (und der später unter dem Pseudonym Bachman als THE RUNNING MAN veröffentlicht wurde). King schickte ihn an den Verlag Ace, doch der SF-Herausgeber Donald A. Wollheim war „nicht an negativen Utopien interessiert“.
Die finanzielle Lage der Kings hatte sich nicht grundlegend gebessert; die Verkäufe von Kurzgeschichten an Magazine (wie zum Beispiel „The Fifth Quarter“, die er 1972 unter dem Pseudonym John Swithen in Cavalier veröffentlichte), ermöglichten es der Familie, sich gerade so über Wasser zu halten. Die Geburt des zweiten Kindes, Joseph Hill, am 4. Juni 1972 verschlimmerte die Lage noch. King begann „zu viel zu trinken“, wie er später schrieb, und im Winter 1972 gingen ihm zu allem Überfluss auch noch die Ideen aus. Er kramte eine im Sommer begonnene Kurzgeschichte mit Titel „Carrie“ hervor, die dann allerdings zu einer völlig unverkäuflichen Novelle anwuchs … und zuerst