Sachverhalt: A. A._ wurde am 20. Januar 2016 durch die Kantonspolizei wegen Verdachts auf Freiheitsberaubung, Nötigung und Körperverletzung festgenommen. Das Zwangsmassnahmengericht Basel-Landschaft versetzte ihn daraufhin für die vorläufige Dauer von zwei Wochen in Untersuchungshaft. Nachdem die Staatsanwaltschaft Basel-Stadt das Verfahren übernommen hatte, verfügte das Zwangsmassnahmengericht am 29. Januar 2016 die Verlängerung der Untersuchungshaft vorläufig bis zum 29. März 2016, wobei der Tatvorwurf um Drohung und versuchte Vergewaltigung erweitert wurde. A._ wird vorgeworfen, B._, mit der er eine heimliche intime Beziehung geführt hat, am 13./14. Januar 2016 in seiner Wohnung in Basel eingesperrt und sie bedroht, beschimpft und geschlagen zu haben. Ausserdem soll er versucht haben, sie zu vergewaltigen. Am 24. März 2016 verlängerte das Zwangsmassnahmengericht die Untersuchungshaft erneut für die vorläufige Dauer von acht Wochen bis zum 24. Mai 2016. Eine dagegen erhobene Beschwerde wies das Appellationsgericht des Kantons Basel-Stadt mit Entscheid vom 20. April 2016 ab. B. Mit Beschwerde in Strafsachen vom 31. Mai 2016 gelangt A._ an das Bundesgericht und beantragt die Aufhebung der Entscheide des Appellationsgerichts vom 20. April 2016 und des Zwangsmassnahmengerichts Basel-Stadt vom 24. März 2016. Er sei umgehend aus der Untersuchungshaft zu entlassen. Eventualiter sei die Sache zum Erlass einer solchen Anordnung an die Vorinstanz zurückzuweisen. Subeventualiter sei ihm bei der Entlassung unter Strafandrohung jeglicher Kontakt zu B._ und ihren Familienmitgliedern zu verbieten. In prozessualer Hinsicht ersucht er um unentgeltliche Rechtspflege. Die Staatsanwaltschaft und das Appellationsgericht schliessen auf Abweisung der Beschwerde. Der Beschwerdeführer hat keine Replik eingereicht.