Rationale: Aspirin-induced asthma (AIA) is a distinct clinical syndrome that affects up to 10% of asthmatic adults. Although eicosanoid metabolites appear to play an important role in AIA, the exact pathogenic mechanism for the syndrome remains obscure. In addition, the proposed mechanism fails to explain why aspirin does not cause bronchoconstriction in all individuals. Objectives: We aimed to identify proteins which were differently expressed in between AIA and ATA plasma. Methods and Main Results: By using a proteomics approach, six proteins were found to be differentially expressed in plasma between AIA and ATA patients at baseline, and eight proteins were significantly up- or down-regulated following aspirin challenge in AIA patients. These proteins, which were identified by MALDI-TOF MS, can be classified into four groups: complement components, apolipoproteins, modified albumin, and unknown proteins. Among them, the complement component levels in plasma were validated by using ELISA. Plasma concentrations of C3a and C4a were higher in patients with AIA (n = 30) than in patients with ATA (n = 24). After the aspirin challenge, C3 decreased in both AIA and ATA patients, but the C3a concentration increased in the AIA patient group (p = 0.019). Moreover, C3a and C4a levels and the ratios of C3a/C3 and C4a/C4 were correlated with the changes of FEV1 values after aspirin challenge. Conclusions: Aspirin intolerance may be related to alterations in the levels of complements, as well as those of lipoprotein and other proteins.