Aside from noting the dramatic rise in their numbers, homicides with unknown victim/offender relationships have attracted little research attention. This study uses Qualitative Comparative Analysis and data from the Supplementary Homicide Reports for 1976 through 1998 to examine the nature of unknown relationship homicides and changes in their structure over time. The findings indicate that a large number of unknown relationship cases are contained within a few prevalent homicide situations while also occurring in a diverse array of less common situations. The situational context of unknown homicides exhibits considerable change over time, shifting from the killing of older White males with a variety of weapons to killings involving young Black males with guns. Although unknown and stranger homicides frequently share common structures, they demonstrate notable differences as well, suggesting that unknown relationships cannot automatically be assumed to involve strangers. Implications of the findings for policy and future research are discussed.