We present late-time Hubble Space Telescope observations of the region surrounding the z≈ 4.5 gamma-ray burst GRB000131, the highest-redshift GRB known. By making an astrometric tie of Very Large Telescope images of the fading afterglow to our late-time HST images we are able to localize the GRB to better than one arcsec precision. In the near vicinity of this localization (<3 arcsec), we detect extended emission in the F616W ( åisebox-0.5ex R) and F805W ( i̊sebox-0.5ex I) filters. The brightness, color, and morphology of this emission are consistent with its identification as an irregular galaxy at z=4.5, and we therefore identify it as the host galaxy of GRB000131. We present a summary of the host galaxy properties deduced from this data, and speculate on the unique prospects of future GRB follow-up efforts to contribute to our understanding of galaxy and star formation processes at high redshift.