Does the magical number four characterize our visual working memory (VWM) capacity for all kinds of objects, or is the capacity of VWM inversely related to the perceptual complexity of those objects? To find out how perceptual complexity affects VWM, we used a change detection task to measure VWM capacity for six types of stimuli of different complexity: colors, letters, polygons, squiggles, cubes, and faces. We found that the estimated capacity decreased for more complex stimuli, suggesting that perceptual complexity was an important factor in determining VWM capacity. However, the considerable correlation between perceptual complexity and VWM capacity declined significantly if subjects were allowed to view the sample memory display longer. We conclude that when encoding limitations are minimized, perceptual complexity affects, but does not determine, VWM capacity.