It comes directly from the French "toute suite", which literally means "all in following" or something like that but which means in actual usage "immediately, all at once". The expression was Anglicised -- probably as far back as the 17th century I imagine-- and shows up in the jargon of soldiers, smugglers, and old folks. :>)

A