Medline has the potential to significantly improve medical care but effective information retrieval remains difficult. Custom interfaces and relevance feedback are two approaches that have been successfully used to improve information retrieval. There are, however, many ways to implement these approaches. A system that facilitates rapid implementation and evaluation of novel algorithms has the potential to speed research progress. This paper describes MedlineQBE, a research workbench for implementing and evaluating information retrieval strategies. User interface, database access and display of results are abstracted leaving developers with the task of coding only the algorithm of interest. We implemented several custom interfaces, search-refinement strategies and a result-ordering algorithm using MedlineQBE. Preliminary evaluations of an oncology-patient interface and a relevance feedback algorithm that builds upon PubMed's "related articles" feature are promising. We conclude that custom interfaces and novel relevance feedback strategies have the potential to improve information retrieval from Medline.