Alternate deposition of oppositely charged polyelectrolytes is an excellent approach to control the chemistry of interfaces. Membrane technology is one field that benefits from the simplicity and tunability of polyelectrolyte multilayers (PEMs). Herein, ultrafiltration support membranes are coated with PEMs to fabricate nanofiltration membranes. Three PEMs, of different polymeric structures, namely, those of poly(4-styrene sulfonate) (PSS)/poly(allylamine hydrochloric acid) (PAH), PSS/poly(ethyleneimine) (PEI, branched), and PSS/poly(4-aminostyrene) (PAS), are prepared and studied from a fundamental perspective in terms of multilayer composition and cross-linking and also from an applied perspective through PEM membrane performance. The low molecular weight cutoff (MWCO) of the PSS/PAH membranes signifies their dense structure (small mesh size), while ion retentions indicate that the dielectric exclusion mechanism is dominant. The PSS/PEI membranes are even denser and have higher selectivities. In contrast, the PSS/PAS membranes are more open, which is likely due to the lower charge density of PAS compared to PEI and PAH. After chemical cross-linking, all of the PEM membranes are denser and therefore more selective and less permeable to water. Micropollutant retention increases for cross-linked PSS/PAH membranes, whereas little to no improvement is seen for cross-linked PSS/PAS and PSS/PEI membranes. Overall, this study shows that completely different membrane properties can be obtained by changing the type of polycation, thus demonstrating the high versatility of PEM-based membranes. In addition, for all PEM membranes, cross-linking acts as an additional tuning parameter that leads to denser and typically more selective layers.