Looking at the OED entry, apparently, the phrase was originally 'of the sudden', but this fell out of fashion for lord knows what reason.
Here's some stuff from the OED:
SUDDEN: C. quasi-n. and n.
1. In advb. phr. formed with preps. = SUDDENLY (chiefly in sense 1). a. of a sudden (earlier: of the sudden): now usually with preceding all.
1570 DEE Math. Pref. diijb, I thinke, that none can iustly account them selues Architectes, of the suddeyne. 1590 H. BARROW in Greenwood Coll. Art Dijb, I was..compelled..to answere of the sodaine vnto such articles. 1596 SHAKES. Tam. Shr. I. i. 152 Is it possible That loue should of a sodaine take such hold? a1648 DIGBY Closet Opened (1669) 188 When all is heated through, it [sc. gravy] will quicken of a sudden. 1681-6 J. SCOTT Chr. Life (1747) III. 66 All of a sudden, and without any..previous Instructions, they were heard to speak..in the fifteen several Tongues of fifteen several Nations. 1864 MRS. LLOYD Ladies of Polcarrow 103 And then Prudy, all of a suddent, began to keep company with that little Preventative fellow. 1890 DOYLE White Company xxx, As he gazed, he saw of a sudden a man steal forth from the wood. 1891 FARRAR Darkn. & Dawn xvii, Then all of a sudden appears Caligula, and demands that Claudius should be recognised as his slave.
