The effects of grain boundary- and triple junction-character on intergranular fatigue crack nucleation were studied in coarse-grained polycrystalline aluminum specimens whose grain boundary microstructures were analyzed by SEM-EBSD/OIM technique. Fatigue crack nucleation occurred mainly along grain boundaries and depended strongly on both the grain boundary character and grain boundary configuration with respect to the persistent slip bands. However, it was little dependent on the geometrical arrangements between the grain boundary plane and the stress axis. Particularly, random boundaries become preferential sites for fatigue crack nucleation. The fatigue cracks were also observed at CSL boundaries when the grain-boundary trace on the specimen surface was parallel to persistent slip bands. On the other hand, no intergranular fatigue cracks were observed at low-angle boundaries. The fatigue cracks were observed at triple junctions as well as grain boundaries. Their nucleation considerably occurred at triple junctions where random boundaries were interconnected. The grain boundary engineering for improvement in fatigue property was discussed on the basis of the results of the structure-dependent intergranular and triple junction fatigue crack nucleation.