Faits : A. A._, citoyen guinéen né en 1991, est arrivé en Suisse le 3 juillet 2009, date à laquelle il a demandé l'asile. Le 21 avril 2010, l'Office fédéral des migrations a rendu une décision de non-entrée en matière et de renvoi de Suisse en Espagne. La procédure d'asile a été reprise le 28 juillet 2011. Une nouvelle décision de non-entrée en matière et de renvoi a été rendue le 22 août 2011. Le 20 avril 2016, l'Officier de police du canton de Genève a notifié au prénommé une interdiction d'accès au canton de Genève pour une durée de 12 mois. Le casier judiciaire de A._ fait état de 17 condamnations entre le 13 janvier 2010 et le 30 novembre 2015, principalement pour violation des art. 115 et 119 de la loi fédérale sur les étrangers du 16 décembre 2005 (LEtr; RS 142.20). S'ajoute à cela que, par jugement du 22 septembre 2016, le Tribunal de police du canton de Genève a condamné le prénommé à une peine privative de liberté de six mois, à une peine pécuniaire de 15 jours-amende ainsi qu'à une amende de 300 francs pour infractions à l'art. 19 de la loi sur les stupéfiants (LStup), séjour illégal (art. 115 LEtr), non-respect d'une interdiction de pénétrer dans une région déterminée (art. 119 al. 1 LEtr), empêchement d'accomplir un acte officiel (art. 286 CP) et consommation de stupéfiants (art. 19a ch. a LStup) : l'intéressé a annoncé faire appel de ce jugement le 28 septembre 2016. B. Par ordonnances pénales des 19 août, 10 septembre et 26 septembre 2016, le Ministère public du canton de Genève (Tmc) a condamné A._ pour infractions aux art. 115 al. 1 let. b et 119 al. 1 LEtr à une peine privative de liberté respectivement de 90 jours, de 80 jours et de 100 jours. L'intéressé a formé opposition à ces trois ordonnances. Par ordonnance du 27 septembre 2016, le Ministère public a joint ces procédures. Par ordonnance du 26 septembre 2016, le Tribunal des mesures de contrainte du canton de Genève (Tmc) a ordonné la mise en détention provisoire du prénommé jusqu'au 26 octobre 2016. Par arrêt du 11 octobre 2016, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours formé par A._ contre l'ordonnance du 26 septembre 2016. En substance, la cour cantonale a considéré que les charges étaient suffisantes, que le risque de fuite et de réitération existait et que le principe de la proportionnalité était respecté. C. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt du 11 octobre 2016 et d'ordonner sa libération immédiate. Il conclut subsidiairement au prononcé que la mise en détention ne repose sur aucune charge suffisante. Il requiert encore l'assistance judiciaire. La Cour de justice renonce à se déterminer et se réfère à l'arrêt attaqué, alors que le Ministère public conclut au rejet du recours.