When applying for the Credit Card what repayment option did you go for? was it the minimum? You say you want the card for the convenience for flights and online shopping, Perhaps you would have a better chance if you opted for a lower limit (e.g.€1000) with a high percentage repayments, ideally if you can afford it 100% of the balance each month. Once you prove to them that you can make that level of payments each month they might be willing to give you a higher limit and reduce the percentage repayments. Just something to consider as if you switch banks you might have to wait a while before they'll give you a credit card either.