Faits : A. Par ordonnance pénale du 1er novembre 2015, A._ a été reconnu coupable d'infraction à l'art. 115 al. 1 let. b et c de la loi fédérale du 16 décembre 2005 sur les étrangers (LEtr; RS 142.20), ainsi que d'empêchement d'accomplir un acte officiel (art. 286 al. 1 CP). Il a été condamné à une peine privative de liberté de 90 jours - sous déduction d'un jour de détention avant jugement - et à une peine pécuniaire de 15 jours-amende à 30 fr. le jour-amende. Le 11 novembre 2015, agissant par l'intermédiaire de son mandataire, le prévenu a formé opposition contre cette décision. Dans ce même courrier, A._ a requis l'octroi de l'assistance judiciaire. Cette demande a été rejetée le 13 novembre 2015, au motif que la cause ne présentait pas de difficultés particulières en droit ou de fait, qu'elle était de peu de gravité vu les peines encourues et qu'ainsi la désignation d'un avocat d'office ne pouvait être exigée. Le recours intenté par le prévenu le 26 novembre 2015 contre cette décision a été rejeté le 21 mars 2016 par la Chambre pénale de recours de la Cour de justice de la République et canton de Genève. B. Par acte du 3 mai 2016, A._ forme un recours en matière pénale contre cet arrêt, concluant à son annulation, à l'octroi de l'assistance judiciaire et à la nomination de Me Arnaud Moutinot en tant que défenseur. A titre subsidiaire, il demande le renvoi de la cause au Ministère public pour nouvelle décision. Le recourant sollicite également le bénéfice de l'assistance judiciaire. Invités à se déterminer, le Ministère public a conclu au rejet du recours, tandis que la cour cantonale a renoncé à formuler des observations.