We consider modeling spatio-temporally indexed relational data, motivated by analysis of voting data for the United States House of Representatives over two decades. The data are characterized by incomplete binary matrices, representing votes of legislators on legislation over time. The spatial covariates correspond to the location of a legislator's district, and time corresponds to the year of a vote. We seek to infer latent features associated with legislators and legislation, incorporating spatio-temporal structure. A model of such data must impose a flexible representation of the space-time structure, since the apportionment of House seats and the total number of legislators change over time. There are 435 congressional districts, with one legislator at a time for each district; however, the total number of legislators typically changes from year to year, for example due to deaths. A matrix kernel stick-breaking process (MKSBP) is proposed, with the model employed within a probit-regression construction. Theoretical properties of the model are discussed and posterior inference is developed using Markov chain Monte Carlo methods. Advantages over benchmark models are shown in terms of vote prediction and treatment of missing data. Marked improvements in results are observed based on leveraging spatial (geographical) information. © 2013 Elsevier B.V. All rights reserved.