We study the first occurrences of gaps between primes in the arithmetic progression (P): r, r + q, r + 2q, r + 3q, . . . , where q and r are coprime integers, q > r ≥ 1. The growth trend and distribution of the first-occurrence gap sizes are similar to those of maximal gaps between primes in (P). The histograms of first-occurrence gap sizes, after appropriate rescaling, are well approximated by the Gumbel extreme value distribution. Computations suggest that first-occurrence gaps are much more numerous than maximal gaps: there are O(log² x) first-occurrence gaps between primes in (P) below x, while the number of maximal gaps is only O(log x). We explore the connection between the asymptotic density of gaps of a given size and the corresponding generalization of Brun's constant. For the first occurrence of gap d in (P), we expect the end-of-gap prime p ≍ √d exp√d/φ(q) infinitely often. Finally, we study the gap size as a function of its index in the sequence of first-occurrence gaps.