Sachverhalt: A. Die Staatsanwaltschaft II des Kantons Zürich, handelnd durch Staatsanwalt B._, führt eine Strafuntersuchung gegen A._ wegen u.a. Betrugs. Sie wirft ihm vor, seit 1. Juni 2005 unter Vortäuschung einer psychischen Erkrankung eine Rente der Invalidenversicherung (IV) unrechtmässig bezogen zu haben. B. Mit Eingabe vom 5. November 2015 verlangte A._ den Ausstand von Staatsanwalt B._. Dieser nahm dazu gestützt auf Art. 58 Abs. 2 StPO am 17. November 2015 Stellung und übermittelte die Untersuchungsakten an die III. Strafkammer des Obergerichts des Kantons Zürich. Am 11. Januar 2016 wies diese das Ausstandsgesuch ab. C. Mit Beschwerde in Strafsachen vom 11. Februar 2016 ans Bundesgericht beantragt A._, der Beschluss des Obergerichts vom 11. Januar 2016 sei aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Eventualiter sei Staatsanwalt B._ in den Ausstand zu setzen und es seien die entsprechenden Untersuchungshandlungen durch eine unabhängige Amtsperson zu wiederholen. In prozessualer Hinsicht ersucht er um unentgeltliche Rechtspflege. Die Staatsanwaltschaft und das Obergericht verzichten auf eine Stellungnahme. B._ (Beschwerdegegner) hat sich nicht vernehmen lassen.