Members of the LuxI protein family catalyze synthesis of acyl-homoserine lactone (acyl-HSL) quorum sensing signals from S-adenosyl-L-methionine and an acyl thioester. Some LuxI family members prefer acyl-CoA, and others prefer acyl-acyl carrier protein (ACP) as the acyl-thioester substrate. We sought to understand the evolutionary history and mechanisms mediating this substrate preference. Our phylogenetic and motif analysis of the LuxI acyl-HSL synthase family indicates that the acyl-CoA-utilizing enzymes evolved from an acyl-ACP-utilizing ancestor. To further understand how acyl-ACPs and acyl-CoAs are recognized by acyl-HSL synthases we studied BmaI1, an octanoyl-ACP-dependent LuxI family member from Burkholderia mallei, and BjaI, an isovaleryl-CoA-dependent LuxI family member from Bradyrhizobium japonicum. We synthesized thioether analogs of their thioester acyl-substrates to probe recognition of the acyl-phosphopantetheine moiety common to both acyl-ACP and acyl-CoA substrates. The kinetics of catalysis and inhibition of these enzymes indicate that they recognize the acyl-phosphopantetheine moiety and they recognize non-preferred substrates with this moiety. We find that CoA substrate utilization arose through exaptation of acyl-phosphopantetheine recognition in this enzyme family.