V týchto ťažkých časoch sa Krupská ďalej starala o rozširovanie robotníckych krúžkov, získala na ich vedenie nových ľudí. Bola členkou ústrednej skupiny, uznávanou pracovníčkou zväzu boja. V lete 1896 z poverenia zväzu boja išla Krupská do Poltavy, kde sa stretla s ukrajinskými marxistami. Dohodla sa s nimi o príprave zjazdu strany a vydávaní spoločných ilegálnych novín. Čoskoro sa musela vrátiť späť do Petrohradu z dôvodu mohutného štrajku petrohradských textilných robotníkov. Krupská sa do vedenia štrajku zapojila s energiou. Zabezpečovala spojenie zväzu boja s organizátormi štrajku v petrohradských továrňach. Revolučná činnosť Krupskej, jej vynachádzavosťou a odvahou si získala sympatie „súdruhov“. Rast jej aktivity v petrohradských sociálnodemokratických kruhov znepokojovalo policajné úrady. Začiatkom jesene 1896 sa meno Krupskej objavuje v policajných hláseniach. Krupskú zatkli pre podozrenie, že je v spojení s pracovníkmi Zväzu boja za oslobodenie robotníckej triedy a že robí propagandu medzi robotníkmi. Avšak vyšetrovatelia nemali priame dôkazy, Nadeždu Konstantinovnu z väzby prepustili. Dali ju však pod osobitný policajný dozor. Krupská aj napriek tomu neprerušila revolučnú činnosť. Znova nadviazala prerušené spojenie so zväzom boja, čo spôsobilo jej druhé zatknutie.

Krupská vo väzení pokračovala v písaní s Leninom. Veľa pracovala, samostatne študovala angličtinu. Jej matka Jelizaveta Vasilievna ťažko prežívala jej zatknutie, a pod zámienkou svojej choroby sa pokúšala dosiahnuť, aby ju čím skôr oslobodili. No jej žiadosti boli nepovšimnuté. Prepustená bola 12. marca 1897, ešte pred vynesením rozsudku. Po vyslobodení sa okamžite znova zapájala do činnosti zväzu boja. Pravidelne písala Leninovi do vyhnanstva do dediny Šušenskoje.

Koncom decembra 1897 oznámili Krupskej rozsudok: tri roky vyhnanstva v Ufskej gubernii. Krupská podala žiadosť na ministerstvo vnútra, aby mohla ísť do dediny Šušenskoje, odôvodnila to tým, že sa ide vydávať za politického vyhnanca Vladimíra Iľjiča Uľjanova, žiadala aj o skrátenie vyhnanstva na dva roky, keďže Leninovi sa končilo vyhnanstvo v roku 1900. Povolenie ísť do Šušenského dostala, ale termín jej neskrátili. V polovici apríla 1898 sa vybrala Nadežda spolu s matkou Jelizavetnou Vasilievnou, ktorá sa rozhodla znášať vyhnanstvo spolu s dcérou, do Šušenkoje.

10. júla 1898 Nadežda Konstantinovna a Vladimír Iľjič uzavreli manželstvo. Musela sa hneď vydať, to bola podmienka policajného odboru. V tej dobe bol povinný cirkevný sobáš. Od sobáša závisela aj podpora, ktorú dostávali vyhnanci. Po uzavretí manželstva dostávala Krupská 8 rubľov mesačne. Po sobáši sa celá rodina presťahovala do domu vdovy Petrovovej. Vo vyhnanstve bola Nadežda Konstantinovna Vladimírovi Iľjičovi prvou pomocníčkou v jeho obrovskej teoretickej práci. Lenin tam napísal vyše tridsať prác. Dokončil svoju kľúčovú prácu Vývoj kapitalizmu v Rusku, ktorou dovŕšil ideovú porážku národníctva a „legálneho marxizmu“. Táto práca bola bezprostredným pokračovaním Marxovho Kapitálu a ďalším rozvinutím ekonomického učenia marxizmu. Nadežda bola jej prvou čitateľkou a prvou kritičkou. Aj vo vyhnanstve sa prejavila ako stranícka pracovníčka. Bola Leninovou pomocníčkou a tajomníčkou. Viedla jeho pracovnú korešpondenciu, legálnu aj ilegálnu. Udržiavala spojenie s inými miestami. Život a práca po Leninovom boku boli pre Krupskú prípravou na ďalšiu revolučnú činnosť. Vo vyhnanstve čítala a študovala Marxove a Engelsove diela, oboznamovala sa s mnohými Leninovými prácami, učila sa angličtinu, nemčinu a poľštinu. Vladimír Iľjič si vážil Nadeždu Konstantinovnu ako vzdelanú marxistku, a tak jej zveroval svoje myšlienky a tvorivé plány, debatoval s ňou o pláne založiť stranu, že treba založiť celoruské ilegálne politické noviny.