Comandante del genio Russo, una persona che, solo per quanto seppe fare a Sebastopoli, merita un posto d'onore tra i grandi costruttori di fortificazioni. Entrato nell'esercito russo nel 1836, Todleben aveva alle spalle una lunga pratica quale ufficiale del Genio. Messo di fronte alla disastrosa situazione di Sebastopoli, si diede con grande energia a costruire una cintura di ridotte in terra, di ripari antiproietto, di barricate, di muri con feritoie, di piazzole d'artiglieria, lunette e parapetti. Continuò a rafforzare le proprie opere durante l'assedio stesso, tanto che al termine delle operazioni le difese della piazza erano più formidabili di quanto non lo fossero all'inizio. I Russi disponevano, in partenza, di 172 cannoni contro 126 degli alleati; alla fine dell'assedio, potevano schierarne 982 di fronte a 800 circa delle forze assedianti.

Gli alleati, per la verità, avevano essi stessi posto le premesse per tale rafforzamento trascurando di isolare la piazzaforte dal suo retroterra e di intercettare i rifornimenti che vi pervenivano. Il bombardamento delle artiglierie alleate danneggiava le difese, ma Todleben mantenne costantemente al lavoro tra i 5000 e i 10.000 uomini con l'unico incarico di riparare ed estendere le opere difensive. Nella maggior parte degli assedi, questo lavoro di riparazione andava compiuto dalle stesse truppe combattenti, a scapito del loro sonno e del tempo per mangiare, ma a Sebastopoli, con una guarnigione di 80.000 uomini, c'era abbondanza di truppe disponibili per opere di ingegneria, con il risultato che Todleben, con le sue squadre, era in grado di riparare durante la notte i danni inferti durante il giorno dal bombardamento, costringendo gli assedianti, giorno per giorno, a riaccanirsi sempre sulle stesse fortificazioni che avevano martellato il giorno prima. Era anche in grado di scavare velocemente reti di trincee, impedendo così agli attaccanti di avvicinarsi troppo alle difese e di lanciare un assalto da posizioni favorevoli.

Le piazzole di artiglieria di Sebastopoli non erano solo i punti di snodo di una semplice cortina difensiva: essi divennero i perni di un vero e proprio sistema complesso di difese, scaglionato in profondità. I 349 giorni di resistenza della città all'assedio alleato furono in gran parte dovuti al genio di Todleben. La disastrosa situazione degli assedianti impedì loro anche solo di pensare un assalto alla fortezza prima del giugno 1855. Gli Inglesi, con britannica ,mancanza di tatto, riuscirono infine a persuadere i loro alleati francesi a scatenare l'assalto il 18 giugno, anniversario della battaglia di Waterloo, e dunque degno giorno da celebrare.

Il risultato fu catastrofico, e costrinse gli assedianti a ripiegare sul tradizionale sistema di parallele e mine. Alla fine, dopo aver scavato una mina fino a 25 m all'interno della Torre Malakov, una struttura in muratura che si era meritata l'appellativo di "Gibilterra della difesa", i Francesi poterono dare il via a un secondo assalto, mentre contemporaneamente gli Inglesi attaccavano il Redan, un poderoso terrapieno difensivo, allo scopo di impegnare il maggior numero possibile di difensori e di impedire loro di rafforzare la Torre Makalov. Il generale Pelissier, comandante francese, aveva osservato che il cambio alla Torre Makalov avveniva regolarmente a mezzogiorno e che, a causa delle complicazioni poste dalla presenza delle traverse e delle compartimentazioni difensive, esisteva un momento di vuoto in cui i vecchi difensori avevano già abbandonato le postazioni mentre i nuovi non vi erano ancora installati.

L'attacco venne perciò programmato esattamente al momento in cui la guarnigione smontava: in quel preciso istante fu scagliata conto le mura la forza dirompente di ben 45.000 uomini, più altri 600 reggenti le scale e gli altri mezzi necessari per poter scavalcare le mura. Il piano di Pelissier ebbe successo. Proprio mentre i difensori abbandonavano la fortificazione, le truppe francesi vi si riversavano a valanga, riuscendo poi a barricarvisi in modo abbastanza solido da respingere i successivi contrattacchi della guarnigione russa. La piccola forza d'assalto inglese, severamente impegnata, finì invece per dover retrocedere, ma assolse comunque il compito diversivo assegnatole, assorbendo contingenti russi che avrebbero altrimenti potuto essere scagliati contro gli alleati all'assalto della Torre Makalov.

Caduto il caposaldo costituito dalla Torre Makalov, il resto della piazzaforte diventava intenibile; di conseguenza quella notte stessa le forze russe abbandonarono il Redan, facendo saltare quanto non era trasportabili, affondarono le imbarcazioni ormeggiate nel porto, incendiarono la città e si ritirarono nell'entroterra. L'assedio, e con lui la guerra, era virtualmente finito.  

I russi ricorsero ancora all'abilità del Todleben durante la guerra russo-turca del 1877, per completare l'assedio di Pleven, in mano ai turchi.  Dopo la guerra fu governatore di Vilnius. Scrisse Défense de Sébastopol (4 voll., 1864-75).